LINEAR SEARCH ON UNSORTED LIST

def linear_search(L, e):
    found = False
    for i in range(len(L)):
        if e == L[i]:
            found = True
    return found

linear_search([1,2,6,867,123,99],6)

True

linear_search([1,2,6,867,123,99],76)

False

• must look through all elements to decide it’s not there
• overall complexity is O(n) – where n is len(L)

LINEAR SEARCH ON SORTED LIST

def search(L, e):
    for i in range(len(L)):
        if L[i] == e:
            return True
        if L[i] > e:
            return False
    return False

search([1,2,6,867,1234],6)

True

search([1,2,6,867,1234],99)

False

search([1,2,157,6,867,1234,0,17891],0) # list is not sorted hence False

False

• must only look until reach a number greater than e
• O(len(L)) for the loop * O(1) to test if e == L[i]
• overall complexity is O(n) –where n is len(L)

BISECTION SEARCH

• finish looking through list when

    - 1 = n/2^i
    - so i= log n

• complexity is O(log n) –where n is len(L)

#BISECTION SEARCH IMPLEMENTATION 1

def bisect_search1(L, e):
    if L == []:
        return False
    elif len(L) == 1:
        return L[0] == e
    else:
        half = len(L)//2
        if L[half] > e:
            return bisect_search1( L[:half], e)
        else:
            return bisect_search1( L[half:], e)

#BISECTION SEARCH IMPLEMENTATION 2

def bisect_search2(L, e):
    def bisect_search_helper(L, e, low, high):
        if high == low:
            return L[low] == e
        mid = (low + high)//2
        if L[mid] == e:
            return True
        elif L[mid] > e:
            if low == mid: #nothing left to search
                return False
            else:
                return bisect_search_helper(L, e, low, mid -1)
        else:
            return bisect_search_helper(L, e, mid + 1, high)
    if len(L) == 0:
        return False
    else:
        return bisect_search_helper(L, e, 0, len(L) -1)

COMPLEXITY OF THE TWO BISECTION SEARCHES

Implementation 1 –bisect_search1

• O(log n) bisection search calls
• O(n) for each bisection search call to copy list
• O(n log n)
• O(n) for a tighter bound because length of list is halved each recursive call

Implementation 2 –bisect_search2 and its helper

• pass list and indices as parameters
• list never copied, just re-passed
• O(log n)

• using linear search, search for an element is O(n)
• using binary search, can search for an element in O(logn)
  • assumes the list is sorted!

BOGO SORT

• best case: O(n) where n is len(L) to check if sorted
• worst case: O(?) it is unbounded if really unlucky

def bogo_sort(L):
    while not is_sorted(L):
        random.shuffle(L)

BUBBLE SORT

• compare consecutive pairs of elements
• swap elements in pair such that smaller is first
• when reach end of list, start over again
• stop when no more swaps have been made

def bubble_sort(L):
    swap = False
    while not swap:
        swap = True
        for j in range(1, len(L)):
            if L[j-1] > L[j]:
                swap = False
                temp = L[j]
                L[j] = L[j-1]
                L[j-1] = temp

O(n^2) where n is len(L)

SELECTION SORT

first step

• extract minimum element
• swap it with element at index 0

subsequent step

• in remaining sublist, extract minimum element
• swap it with the element at index 1

keep the left portion of the list sorted

• at ith step, first ielements in list are sorted
• all other elements are bigger than first ielements

def selection_sort(L):
    suffixSt= 0
    while suffixSt!= len(L):
        for i in range(suffixSt, len(L)):
            if L[i] < L[suffixSt]:
                L[suffixSt], L[i] = L[i], L[suffixSt]
        suffixSt+= 1

• outer loop executes len(L) times
• inner loop executes len(L) –i times
• complexity of selection sort is O(n^2) where n is len(L)

MERGE SORT

use a divide-and-conquer approach:

• if list is of length 0 or 1, already sorted
• if list has more than one element, split into two lists, and sort each
• merge sorted sublists
  • look at first element of each, move smaller to end of the result
  • when one list empty, just copy rest of other list

def merge(left, right):
    result = []
    i,j= 0, 0
    while i< len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i+= 1
        else:
            result.append(right[j])
            j += 1
        #print(result,'result')
    while (i< len(left)):
        result.append(left[i])
        i+= 1
    while (j < len(right)):
        result.append(right[j])
        j += 1
    return result

def merge_sort(L):
    if len(L) < 2:
        return L[:]
    else:
        middle = len(L)//2
        #print(middle,'middle')
        #print(L[:middle],'ll')
        #print(L[middle:],'rl')
        left = merge_sort(L[:middle])
        #print(left,'left')
        right = merge_sort(L[middle:])
        #print(right,'right')
        return merge(left, right)

merge_sort([0,1,5,6,3,7,4])

[0, 1, 3, 4, 5, 6, 7]

COMPLEXITY OF MERGING SUBLISTS STEP

• go through two lists, only one pass
• compare only smallest elements in each sublist
• O(len(left) + len(right)) copied elements
• O(len(longer list)) comparisons
• linear in length of the lists

• divide list successively into halves
• depth-first such that conquer smallest pieces down one branchfirst before moving to larger pieces

COMPLEXITY OF MERGE SORT

at first recursion level

• n/2 elements in each list
• O(n) + O(n) = O(n) where n is len(L)

at second recursion level

• n/4 elements in each list

• two merges O(n) where n is len(L)

• each recursion level is O(n) where n is len(L)

• dividing list in half with each recursive call
• O(log(n)) where n is len(L)
• overall complexity is O(n log(n)) where n is len(L)

SORTING SUMMARY--n is len(L)

bogosort

• randomness, unbounded O()

bubble sort

• O(n2)

selection sort

• O(n2)
• guaranteed the first i elements were sorted

merge sort

• O(n log(n))
• O(n log(n)) is the fastest a sort can be

---

Reference

• edX course offered by MIT
• 6.00.1x Introduction to Computer Science and Programming Using Python